#ifndef __INTERSECTIONLISTNODE_H__
#define __INTERSECTIONLISTNODE_H__
#include "ListHeader.h"

/*
* leetcode 02.07 链表相交
* 判断链表是否相交, 若相交, 则返回相交节点; 否则返回 nullptr
*/

/*
* 具体做法为: 计算两条链表的长度, 将较长的链表移动相差的长度
* 然后移动两条链表的指针, 若相等, 则相交; 否则不相交
*/

//根据相交链表的特性, 可以判断相交的节点在 末尾 的长度差中
List* IntersectionListNode(List* list1, List* list2) {
	List* l1 = list1;
	List* l2 = list2;

	unsigned int sizeL1 = 0;
	unsigned int sizeL2 = 0;

	while (l1 != nullptr) {
		l1 = l1->next;
		sizeL1++;
	}
	while (l2 != nullptr) {
		l2 = l2->next;
		sizeL2++;
	}

	//计算长度差
	unsigned int sizeMove = sizeL1 > sizeL2 ? sizeL1 - sizeL2 : sizeL2 - sizeL1;
	List* move = sizeL1 > sizeL2 ? list1 : list2;
	List* compare = sizeL1 > sizeL2 ? list2 : list1;

	//末尾对齐, 此时两个链表距离末尾的距离相同, 同时相交的节点也在末尾
	// (不可能在前面, 因为末尾已经对其)
	while (sizeMove > 0) {
		move = move->next;
		sizeMove--;
	}
	while (compare != nullptr) {	//移动, 判断是否相等, 相等即为相交节点
		if (compare == move)
			return compare;

		compare = compare->next;
		move = move->next;
	}

	return nullptr;
}

#endif // !__INTERSECTIONLISTNODE_H__

